package com.yulongtian.offers.day202209.day20220922;

/**
 * https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/?plan=lcof&plan_progress=g8d07hi
 *
 * @author YulongTian
 * @date 2022/9/22 - 16:39
 */
public class Test05 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(5);

        ListNode l2 = new ListNode(1);
        ListNode a2 = new ListNode(2);
        ListNode b2 = new ListNode(4);
        l2.next = a2;
        a2.next = b2;

        ListNode listNode = mergeTwoLists(l1, l2);

        ListNode p = listNode;
        while (p != null) {
            System.out.print(p.val + ",");
            p = p.next;
        }

    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null&&l2==null){
            return l1;
        }
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode p1 = l1;
        ListNode q1 = l1;
        ListNode p2 = l2;
        boolean flag=false;
        while (p1 != null && p2 != null) {

            while (p1!=null){
                if(p2.val<p1.val){
                    if(p1==q1){
                        ListNode temp = p2.next;
                        p2.next=p1;
                        q1=p2;
                        l1=p2;
                        p2=temp;
                        flag=true;
                        break;
                    }
                    break;
                }
                q1=p1;
                p1=p1.next;
            }

            if(p1==null){
                break;
            }
            if(flag){
                flag=false;
                continue;
            }
            ListNode temp = p2.next;
            p2.next = q1.next;
            q1.next = p2;
            p2 = temp;
            q1 = q1.next;
            if(p2==null){
                break;
            }
        }

        if(p1==null){
            q1.next=p2;
        }


        return l1;
    }


}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
